1. Field of the Invention
The present invention relates to a reconfigurable device in which various functions can be implemented by a user, and in particular to a function block which is a logic function constituting unit. More specifically, the present invention relates to a function block suitable for implementing a multiplier and a multiplexer. In this specification, a circuit bearing a main portion of a logic function in a programmable function cell is referred to as a function block.
2. Description of the Related Art
Recently, reconfigurable devices such as a PLD (programmable logic device), FPGA (field programmable gate array) and the like in which various functions can be set by a user have been rapidly developed. With increase of degree of integration and speed, such a reconfigurable device is expected to be used not only for emulation during the designing of ASIC (application-specific integrated circuit) or substitution of a simple peripheral circuit but also for a reconfigurable computer whose hardware structure can be changed depending on an application.
However, a multiplier that is frequently used in computing cannot be effectively realized by a conventional PLD or FPGA, which is one of tho causes disturbing practical use of a reconfigurable computer. Furthermore, the conventional PLD and FPGA cannot effectively realize a multi-input multiplexer (MUX). Owing to this, it has been impossible to obtain a compact barrel shifter, for example, used for floating-point addition/subtraction.
FIG. 103 shows a typical example of an ordinary multiplier. This multiplier multiplies X=x7x6x5x4x3x2x1x0 by Y=y3y2y1y0 to produce Z=z11z10z9z8z7z6z5z4z3z2z1z0 that is the product of X and Y, where each of xi, yi or zi represents (i+1)-th bit of binary data X, Y and Z, and is 0 or 1 (ixe2x88x920, 1, 2, . . . ). For example, the notation of x7x6x5x4x3x2x1x0 represents a bit arrangement of binary data X. As is clear from FIG. 103, this multiplier is constructed by systematically arranging a multiplier unit 76 in an array. In the multiplier unit 76, an output of an AND circuit 31 is connected to one argument input b of a 1-bit full adder 43. In the 1-bit full adder 43 of FIG. 103, the other argument input is denoted by a, a carry input by ic, a carry output by oc, and an addition output by s. The multiplier as shown in FIG. 103 is the most basic array-type multiplier having a simple and systematic configuration, which is suitable for implementation in the FPGA.
FIG. 104 shows an example of a conventional function block 4 for FPGA (for example, see U.S. Pat. Nos. 5,349,250, 5,481,206, and 5,546,018). Here, only those parts related to the description are shown. In the figure, a logic function generator 40 is a circuit capable of realizing various logic functions in accordance with contents of a built-in configuration memory.
FIG. 105 shows an example of the logic function generator 40. This has sixteen 1-bit memory cells 13 as a configuration memory and the outputs of respective ones of the memory cells are inputted to a 16-input multiplexer (MUX) 20. In accordance with values of four control inputs in0, in1, in2 and in3, the 16-input MUX 20 selects one of the 16 inputs to output it as denoted by out. This logic function generator 40 has a logic function which is determined in accordance with contents stored in the configuration memory 13 and can realize an arbitrary 4-input 1-output logic function having four inputs in0, in1, in2 and in3 and one output. In general, a logic function generator having 2 k-bit memory cells and capable of realizing all the k-input 1-output logic functions is referred to as a Look-Up Table (hereinafter, abbreviated as LUT). FIG. 105 shows an example of 4-input LUT. Examples of other configurations of the LUT are disclosed in, for example, U.S. Re. Pat. No. 34,363 and U.S. Pat. No. 4,706,216.
The function block 4 of FIG. 104 uses the logic function generator 40 to which a 2-input MUX 22 as a ripple carry circuit and a 2-input exclusive OR circuit (XOR) 30 required for constituting an adder are added.
With regard to the 2-input MUX, see FIG. 7. In FIG. 7, the 2-input MUX 22 has an input to which input in0 is connected (input-0) and another input to which input in1 is connected (input-1). When a control input in2 is logical 0, a signal in0 fed to the input-0 is outputted as denoted by out, and when the control input in2 is logical 1, a signal in1 fed to the input 1 is outputted. Hereinafter, when MUX is briefly written as xe2x80x9cMUXxe2x80x9d omitting the number of inputs, it represents two inputs (exclusive of a control input).
The multiplier of FIG. 103 may be configured using the function block 4 of FIG. 104 to implement the function as shown in FIG. 106 in the logic function generator 40 of FIG. 104. In this case, the function block 4 of FIG. 104 functions as the multiplier unit 76 of FIG. 103. Here, an input in0, an output os, a ripple carry input irc, and a ripple carry output orc of FIG. 104 correspond to the argument input a, the adder output s, the carry input ic, and the carry output oc of the 1-bit full adder 43, respectively. Moreover, the AND 31 in the circuit of FIG. 106 implemented in the logic function generator 40 of FIG. 104 corresponds to the AND 31 in the multiplier unit 76 of FIG. 103.
As has been described above, the multiplier unit 76 of FIG. 103 can be constructed of one function block 4 of FIG. 104. However, when a multiplier is constructed by this method, multiplication of m-bit data and n-bit data requires mxc3x97n function blocks, occupying a great area. Furthermore, in the case of a multiplier of n bits, a signal should be transferred through n stages of function blocks 4 (besides a carry propagation delay) and accordingly, a signal propagation delay is also increased.
In addition to the function block shown in FIG. 104, several methods have been devised for realizing by a single function block a multiplier unit in which an AND gate is attached to one argument input of a 1-bit full adder (for example, see Japanese Patent Application Laid-open Publication Nos. 11-24891, 11-122096, and 11-353152, and U.S. Pat. No. 5,570,039). These conventional techniques also have the aforementioned problem.
In order to solve the aforementioned problem, U.S. Pat. No 5,754,459 discloses a method for implementing a multiplier using the modified Booth algorithm and the Wallace Tree into a PLD. However, this multiplier has disadvantages that its circuit configuration is complicated, a plenty of wiring resources is needed, and the area reduction effect is small.
Furthermore, the conventional FPGA has a problem that multi-input (3-input or more in this specification) MUX cannot be effectively realized. As shown in FIG. 104, in the function block 4 having one 4-input logic function generator 40, only one 2-input MUX which is the simplest can be implemented. This is because a 2-input MUX can be realized by three input terminals including a control input while a 3-input MUX requires 5 input terminals and a 4-input MUX requires 6 input terminals. Thus, the 4-input logic function generator cannot provide a sufficient number of inputs.
From this reason, for example, for realizing a 4-input MUX having a high usability by the conventional FPGA, as shown in FIG. 107, it is necessary to use two function blocks 4a and 4b and a MUX 22. (FIG. 107 shows only a portion of the function block related to the present explanation). Here, the logic function generator 40 of each function block has a 2-input MUX (for example, as shown in FIG. 7) implemented therein. In this case, in FIG. 107, two pairs of inputs i0 and i1 of the function blocks 4a and 4b correspond to the four inputs of the 4-input MUX, respectively. The respective inputs i2 and i4 correspond to first and second control inputs of the 4-input MUX. An output om corresponds to the output of the 4-input MUX.
Thus, in order to realize a 4-input MUX by using the conventional FPGA, it is necessary to use two function blocks, resulting in an increase in occupied area. Japanese Patent Laid-open Publication No. 11-24891, Japanese Patent Laid-open Publication Nos. 11-122096 and 11-353152 disclose a completely different type of function block not using the 4-input LUT. However, even with this function block, it is impossible to realize a 4-input MUX in one block.
The floating-point addition/subtraction is performed by using a barrel shifter, which is composed of a large number of MUX""es. When implementing it in the FPGA, such a scheme that a single function block corresponds to one 2-input MUX is inefficient, resulting in increased area. It is desired to realize a 4-input MUX with one function block, thereby greatly improving the efficiency.
A first problem is that when a multiplier is configured by using a conventional function block, the multiplier area and signal propagation delay are increased. When a multiplier unit consisting of a 1-bit full adder and an AND gate is made by one function block, it is necessary to use great many function blocks to complete the entire multiplier.
A second problem is that when constructing a multi-input multiplexer using a conventional function block, the area is increased. Since only one 2-input MUX can be implemented in one function block, plural function blocks should be used to constitute a multi-input MUX.
It is therefore an object of the present invention to provide a function block capable of realizing a compact and high-speed multiplier.
Another object of the present invention is to provide a function block capable of realizing a compact multi-input multiplexer.
According to the present invention, a 4-2 carry block is added to a known function block so as to be used as a 4-2 adder. Furthermore, a preposition logic circuit is added so that an AND-attached 4-2 adder can be realized in one function block. Moreover, an XOR (exclusive OR) and an MUX (multiplexer) are combined with each other so as to constitute a function block, which can also be used as an AND-attached 4-2 adder. Furthermore, by using a MUX as a preposition logic circuit, a multi-input MUX (for example, 4-input MUX) can be realized in one function block.
According to a first aspect of the present invention, a function block includes: a logical function generator having four logical input terminals and one logical output terminal, for generating a logical output signal from first, second, third, and fourth logical input signals thereof according to a logical function selected from a plurality of 4-input/1-output logical functions depending on configuration data; a 4-2 carry block for generating a 4-2 carry output signal from the second, third, and fourth logical input signals; a first signal generator for generating a first signal from at least the logical output signal; a second signal generator for generating a second signal from at least the first logical input signal; a third signal generator for generating a third signal from at least a 4-2 carry input signal; a fourth signal generator for generating a fourth signal from at least the 4-2 carry input signal; a selector for selecting one of the second and third signals depending on the first signal to produce a carry output signal; and an exclusive OR circuit for performing an exclusive OR function on the logical output signal and the fourth signal to produce an output of the function block.
Several embodiments of the first-aspect function block are shown in the accompanying drawings, for example, FIGS. 6, 40-42, 45-51, 59 and 61.
Taking FIG. 6 as an example, the respective first, second, third, and fourth logical inputs correspond to inputs in0, in1, in2, and in3 of a logical function generator 40 and the logical output corresponds to an output out of the logical function generator 40.
The first signal generator corresponds to a wire connecting the output out as the first signal to the control input of a MUX 22c that corresponds to the selector. Alternatively, taking FIGS. 40 and 42 as other examples, the first signal generator corresponds to a MUX 22d and/or AND 31d for selecting a signal from the output out, other signal i50, and/or a fixed value to output it as the first signal to the control input of the MUX 22c. 
The second signal generator, as shown in FIG. 6, corresponds to a wire connecting the input in0 as the second signal to the input-0 of the MUX 22c. Alternatively, taking FIG. 42 as another example, the second signal generator corresponds to a MUX 22m for selecting a signal from the inputs in0 and in3 of the logical function generator 40 to output it as the second signal to the input-0 of the MUX 22c. 
The third signal generator, as shown in FIG. 6, corresponds to a wire connecting the 4-2 carry input signal i42 as the third signal to the input-1 of the MUX 22c. Alternatively, taking FIG. 41 as another example, the third signal generator corresponds to a MUX 22g for selecting a signal from the 4-2 carry input signal i42 and the input in3 and a wire connecting the selected signal as the third signal to the input-1 of the MUX 22c. Further, taking FIG. 48 as another example, the third signal generator corresponds to a MUX 22h for selecting a signal from the 4-2 carry input signal i42 and the ripple carry signal irc and a wire connecting the selected signal as the third signal to the input-1 of the MUX 22c. 
The fourth signal generator, as shown in FIG. 6, corresponds to a wire connecting the 4-2 carry input signal i42 as the fourth signal to one input of an XOR 30 that corresponds to the above exclusive OR circuit. In other words, according to the example as shown in FIG. 6, the third and fourth signal generators both use the 4-2 carry input signal 142 as the third and fourth signal, respectively. Alternatively, taking FIG. 41 as another example, the fourth signal generator corresponds to a MUX 22g for selecting a signal from the 4-2 carry input signal i42 and the input in3 and a wire connecting the selected signal as the fourth signal to the one input of the XOR 30. Further, taking FIG. 47 as another example, the fourth signal generator corresponds to a MUX 22h for selecting a signal from the 4-2 carry input signal i42 and the ripple carry signal irc to output the selected signal as the fourth signal to the input-1 of the MUX 22c. Furthermore, taking FIG. 59 as another example, the fourth signal generator corresponds to a MUX 22h for selecting a signal from the 4-2 carry input signal i42 and the input in3 and an AND 31k for selecting one of the selected signal and a fixed value to output it as the fourth signal to the one input of the XOR 30.
According to a second aspect of the present invention, a function block includes: a first exclusive OR circuit for performing an exclusive OR function on a first input signal and a second input signal; a second exclusive OR circuit for performing an exclusive OR function on a third input signal and a fourth input signal; a 4-2 carry block for generating a 4-2 carry output signal from at least, one of the first and second input signals and one of the third and fourth input signals; a third exclusive OR circuit for performing an exclusive OR function on output signals of the first exclusive OR circuit and the second exclusive OR circuit; a first signal generator for generating a first signal from at least an output signal of the third exclusive OR circuit; a second signal generator for generating a second signal from at least one of the first and second input signals; a third signal generator for generating a third signal from a first multiple-signal group including a 4-2 carry input signal and at least one logical input signal; a fourth signal generator for generating a fourth signal from a second multiple-signal group including the 4-2 carry input signal and at least one logical input signal; a selector for selecting one of the second and third signals to produce a carry output signal depending on the first signal; and a fourth exclusive OR circuit for performing an exclusive OR function on the fourth signal and the output signal of the third exclusive OR circuit.
Several embodiments of the second-aspect function block are shown in the accompanying drawings, for example, FIGS. 73, 77-81, and 84-86.
Taking FIG. 73 as an example, the first exclusive OR circuit corresponds to XOR 30a, the second exclusive OR circuit corresponds to XOR 30b, the 4-2 carry block corresponds to a MUX 22j, the third exclusive OR circuit corresponds to XOR 30c, and the fourth exclusive OR circuit corresponds to XOR 30d. 
The first signal generator is basically similar to that of the first-aspect function block. For example, in FIG. 73, the first signal generator corresponds to a wire connecting the output of XOR 30c as the first signal to the control input of a MUX 22c that corresponds to the selector.
The second signal generator is basically similar to that of the first-aspect function block. For example, in FIG. 73, the second signal generator corresponds to a wire connecting one input of XOR 30a as the second signal to the input-0 of the MUX 22c. 
The third signal generator is basically similar to that of the first-aspect function block. For example, in FIG. 73, the third signal generator corresponds to a MUX 22h for selecting a signal from a first multiple-signal group including the 4-2 carry input signal i42 and another logical input signal i40 and a wire connecting the selected signal as the third signal to the input-1 of the MUX 22c. 
The fourth signal generator is basically similar to that of the first,-aspect function block. For example, in FIG. 73, the fourth signal generator corresponds to a MUX 22h for selecting a signal from a second multiple-signal group including the 4-2 carry input signal i42 and another logical input signal i40 and a wire connecting the selected signal as the fourth signal to one input of the XOR 30d. In other words, according to the example as shown in FIG. 73, the third and fourth signal generators select the third and fourth signal from the same multiple-signal group, respectively.